# 96/100 技巧-只出现一次的数字
# leetcode第136题: https://leetcode.cn/problems/single-number/description/?envType=study-plan-v2&envId=top-100-liked
from functools import reduce


def singleNumber_hash(nums: list[int]) -> int:
    """使用哈希的方法, 缺点是空间复杂度为O(N)"""
    exist = set()
    for i, x in enumerate(nums):
        if x in exist:
            exist.remove(x)
        else:
            exist.add(x)
    return exist.pop()


def singleNumber_xor(nums: list[int]) -> int:
    """使用异或运算
    异或操作时一种位运算操作,  它比较两个数的二进制表示中的每一位，当两个相应的二进制位不同时，结果位为1，否则为0。
    例如: 我们有两个整数a = 3和b = 5，它们的二进制表示分别是0b011和0b101，那么它们的异或结果a ^ b将是0b110，即十进制中的6。

    异或操作具有一些特性:
    1.归零率: A ^ A = 0
    2.结合律: (A ^ B) ^ C = A ^ (B ^ C)

    那么我们就可以利用上面的两个特性找到那个只出现一次的数字了:
    A ^ B ^ C ^ A ^ B
    = (A ^ A) ^ (B ^ B) ^ C
    = C

    """
    return reduce(lambda x, y: x ^ y, nums)


if __name__ == '__main__':
    print(singleNumber_xor([2, 2, 1]))  # 1
    print(singleNumber_xor([4, 1, 2, 1, 2]))  # 4
    print(singleNumber_xor([1]))  # 1
